package top.fengleifeng.question;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author : fengleifeng
 * @Package top.fengleifeng.question
 * @Description:
 * @date Date : 2020年12月11日 3:49 下午
 */
public class Num946验证栈序列 {

    class Solution {

        public boolean validateStackSequences(int[] pushed, int[] popped) {
            if(pushed.length<=0){
                return true;
            }
            Stack<Integer> stack = new Stack<>();
            int pushedIndex = 0;//下一个push的索引
            int poppedIndex = 0;//当前pop的index
            stack.add(pushed[pushedIndex++]);
            while (!stack.isEmpty()) {
                int now = stack.peek();
                int poppedValue = popped[poppedIndex];
                if (poppedValue == now) {
                    stack.pop();
                    poppedIndex++;
                } else {
                    if (pushedIndex < pushed.length) {
                        stack.add(pushed[pushedIndex++]);
                    } else {
                        return false;
                    }
                }
                if(stack.isEmpty() && pushedIndex!=pushed.length){
                    stack.add(pushed[pushedIndex++]);
                }
            }
            return true;
        }
    }

    public static void main(String[] args) {
//        int[] ints = {1,2,3,4,5};
//        int[] ints2 = {4,5,3,2,1};
//        int[] ints = {1, 2, 3, 4, 5};
//        int[] ints2 = {4, 3, 5, 1, 2};
        int[] ints = {4,0,1,2,3};
        int[] ints2 = {4,2,3,0,1};
        boolean b = new Num946验证栈序列().new Solution().validateStackSequences(ints, ints2);
        System.out.println(b);
    }
}
